{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimize Deviation in Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #ordered-set #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #有序集合 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumDeviation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组的最小偏移量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由 <code>n</code> 个正整数组成的数组 <code>nums</code> 。</p>\n",
    "\n",
    "<p>你可以对数组的任意元素执行任意次数的两类操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果元素是<strong> 偶数</strong> ，<strong>除以</strong> <code>2</code>\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>例如，如果数组是 <code>[1,2,3,4]</code> ，那么你可以对最后一个元素执行此操作，使其变成 <code>[1,2,3,<strong>2</strong>]</code></li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>如果元素是 <strong>奇数</strong> ，<strong>乘上</strong> <code>2</code>\n",
    "\t<ul>\n",
    "\t\t<li>例如，如果数组是 <code>[1,2,3,4]</code> ，那么你可以对第一个元素执行此操作，使其变成 <code>[<strong>2</strong>,2,3,4]</code></li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>数组的 <strong>偏移量</strong> 是数组中任意两个元素之间的 <strong>最大差值</strong> 。</p>\n",
    "\n",
    "<p>返回数组在执行某些操作之后可以拥有的 <strong>最小偏移量</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>你可以将数组转换为 [1,2,3,<strong>2</strong>]，然后转换成 [<strong>2</strong>,2,3,2]，偏移量是 3 - 2 = 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,1,5,20,3]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>两次操作后，你可以将数组转换为 [4,<strong>2</strong>,5,<strong>5</strong>,3]，偏移量是 5 - 2 = 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,10,8]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 5 * 10<sup><span style=\"font-size: 10.8333px;\">4</span></sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimize-deviation-in-array](https://leetcode.cn/problems/minimize-deviation-in-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimize-deviation-in-array](https://leetcode.cn/problems/minimize-deviation-in-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]', '[4,1,5,20,3]', '[2,10,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        import heapq\n",
    "        nums = [-num*2 if num%2 != 0 else -num for num in nums]\n",
    "        min_value = -max(nums)\n",
    "        heapq.heapify(nums)\n",
    "        ans = -nums[0] - min_value\n",
    "        while nums[0] % 2 == 0:\n",
    "            min_value = min(min_value, -nums[0]/2)\n",
    "            heapq.heapreplace(nums, nums[0]/2)\n",
    "            ans = min(ans, -nums[0] - min_value)\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: list[int]) -> int:\n",
    "        import heapq as hq\n",
    "\n",
    "        heap = []\n",
    "        for n in nums:\n",
    "            if n % 2:\n",
    "                hq.heappush(heap, -2 * n)\n",
    "            else:\n",
    "                hq.heappush(heap, -n)\n",
    "        minVal = -max(heap)\n",
    "        res = -heap[0] - minVal\n",
    "        while heap and heap[0] % 2 == 0:\n",
    "            nxt = hq.heappop(heap) // 2\n",
    "            hq.heappush(heap, nxt)\n",
    "            minVal = min(minVal, -nxt)\n",
    "            res = min(res, -heap[0] - minVal)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        # 正整数，对每个数，两种选择，要么是操作：偶数÷2，奇数 *2，要么是不操作,暴力法 2**n \n",
    "        # 考虑到 *2 和 ÷2 是一对相反的操作，而且我们可以进行任意次这种操作，那么我们可以所有数都预先处理成偶数/奇数，这样我们就只余下一种操作。\n",
    "        pool = [-x * 2 if x & 1 else -x for x in nums]\n",
    "        heapify(pool)\n",
    "        ma, mi = -pool[0], -max(pool)\n",
    "        res = ma - mi \n",
    "        while (-pool[0]) & 1 == 0:\n",
    "            mi = min(mi, -pool[0]//2)\n",
    "            heapreplace(pool, pool[0]//2)\n",
    "            res = min(res, -pool[0] - mi)\n",
    "            # print(ma, mi, res, pool)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        q = []\n",
    "\n",
    "        for x in nums:\n",
    "            if x % 2 == 1:\n",
    "                x *= 2\n",
    "\n",
    "            heappush(q, -x)\n",
    "\n",
    "        mi = -max(q)\n",
    "        ret = inf\n",
    "        while -q[0] % 2 == 0:\n",
    "            x = -heappop(q)\n",
    "            heappush(q, - x // 2)\n",
    "            mi = min(mi, x // 2)\n",
    "\n",
    "            ret = min(ret, -q[0] - mi)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        q = [-num*(num%2+1) for num in nums]\n",
    "        heapq.heapify(q)\n",
    "        mi = max(q)\n",
    "        ans = 1e10\n",
    "        while q[0]%2==0:\n",
    "            h = heapq.heappop(q)\n",
    "            ans = min(ans, mi-h)\n",
    "            mi = max(mi, h//2)\n",
    "            heapq.heappush(q, h//2)\n",
    "        return min(ans, mi-q[0])\n",
    "\n",
    "        # def odd(n):\n",
    "        #     while n%2 == 0:\n",
    "        #         n //=2\n",
    "        #     return [n, False]\n",
    "        # q = list(map(odd, nums))\n",
    "        # heapq.heapify(q)\n",
    "        # i = 0\n",
    "        # ans = 1e10\n",
    "        # mx = max(q)[0]\n",
    "        # while i<len(nums):\n",
    "        #     h = heapq.heappop(q)\n",
    "        #     ans = min(ans, mx-h[0])\n",
    "        #     if not h[1]:\n",
    "        #         i += 1\n",
    "        #     heapq.heappush(q, [2*h[0], True])\n",
    "        #     mx = max(mx, 2*h[0])\n",
    "        #     print(q, ans)\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        nums = [-v * 2 if v & 1 else -v for v in nums]\n",
    "        min_num = -max(nums)\n",
    "        heapify(nums)\n",
    "        diff = -nums[0] - min_num\n",
    "        while diff > 0 and (-nums[0]) & 1 == 0:\n",
    "            min_num = min(min_num, -nums[0]//2)\n",
    "            heapreplace(nums, nums[0]//2)\n",
    "            diff = min(diff, -nums[0] - min_num)\n",
    "            \n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        nums = [-v << 1 if v & 1 else -v for v in nums]\n",
    "        min_num = -max(nums)\n",
    "        heapify(nums)\n",
    "        diff = -nums[0] - min_num\n",
    "        while diff > 0 and (-nums[0]) & 1 == 0:\n",
    "            min_num = min(min_num, (-nums[0]) >> 1)\n",
    "            heapreplace(nums, nums[0] >> 1)\n",
    "            diff = min(diff, -nums[0] - min_num)\n",
    "            \n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        nums = [-e if e%2==0 else -e*2 for e in nums]\n",
    "        min_v = -max(nums)\n",
    "        min_diff = max(nums) - min(nums)\n",
    "        heapq.heapify(nums)\n",
    "        while nums[0]%2==0:\n",
    "            max_v = -heapq.heappop(nums)\n",
    "            max_v = max_v // 2\n",
    "            min_v = min(min_v, max_v)\n",
    "            heapq.heappush(nums, -max_v)\n",
    "            min_diff = min(min_diff, abs(-nums[0] - min_v))\n",
    "            pass\n",
    "        return min_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        ret = float(\"inf\")\n",
    "        biggest_nums = [-i*2 if i%2 else -i for i in nums]\n",
    "        hq.heapify(biggest_nums) # 最大堆\n",
    "        smallest_nums = -max(biggest_nums)\n",
    "        \n",
    "        while ret > 0 and -biggest_nums[0]%2 == 0:\n",
    "            ret = min(ret, -biggest_nums[0]-smallest_nums)\n",
    "            tmp = hq.heappop(biggest_nums) // 2\n",
    "            hq.heappush(biggest_nums,tmp)\n",
    "            smallest_nums = min(smallest_nums, -tmp)\n",
    "        ret = min(ret, -biggest_nums[0]-smallest_nums)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        nums = [-num if num%2==0 else -num*2 for num in nums]\n",
    "        heapq.heapify(nums)\n",
    "        min_val = -max(nums)\n",
    "        res = -nums[0]+max(nums)\n",
    "        while -nums[0]%2 == 0:\n",
    "            tmp = -int(nums[0]/2 )\n",
    "            min_val = min(min_val, tmp)\n",
    "            heapq.heappop(nums)\n",
    "            heapq.heappush(nums, -tmp)\n",
    "            res = min(res, -nums[0]-min_val)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        s = SortedList([i * (i % 2 + 1) for i in nums])\n",
    "        res = s[-1] - s[0]\n",
    "        while not s[-1] & 1:\n",
    "            s.add(s.pop() >> 1)\n",
    "            res = min(res, s[-1] - s[0])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        s=SortedList(x<<1 if (x&1)==1 else x for x in nums)\n",
    "        mn=s[-1]-s[0]\n",
    "        while mn!=0 and not s[-1]&1:\n",
    "            s.add(s.pop()>>1)\n",
    "            mn=min(mn,s[-1]-s[0])\n",
    "        return mn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        s=SortedList(x<<1 if (x&1)==1 else x for x in nums)\n",
    "        mn=s[-1]-s[0]\n",
    "        while mn!=0 and not s[-1]&1:\n",
    "            s.add(s.pop()>>1)\n",
    "            mn=min(mn,s[-1]-s[0])\n",
    "        return mn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        q = SortedList()\n",
    "\n",
    "        for x in nums:\n",
    "            if x % 2 == 1:\n",
    "                x *= 2\n",
    "\n",
    "            q.add(x)\n",
    "\n",
    "        ret = q[-1] - q[0]\n",
    "        while q[-1] % 2 == 0:\n",
    "            x = q.pop(-1)\n",
    "            q.add(x // 2)\n",
    "            ret = min(ret, q[-1] - q[0])\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        sl = SortedList([])\n",
    "        for num in nums:\n",
    "            if num % 2:\n",
    "                sl.add(num * 2)\n",
    "            else:\n",
    "                sl.add(num)\n",
    "\n",
    "        min_dev = sl[-1] - sl[0]\n",
    "        while sl[-1] % 2 == 0:\n",
    "            num = sl.pop(-1)\n",
    "            num //= 2\n",
    "            sl.add(num)\n",
    "            min_dev = min(min_dev, sl[-1] - sl[0])\n",
    "        return min_dev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "\n",
    "        q = []\n",
    "        for num in nums:\n",
    "            if num % 2:\n",
    "                heapq.heappush(q, -num * 2)\n",
    "            else:\n",
    "                heapq.heappush(q, -num)\n",
    "        ans = inf\n",
    "        mi = -max(q)\n",
    "        while q and q[0] % 2 == 0:\n",
    "            cur = -heapq.heappop(q)\n",
    "            ans = min(ans, cur - mi)\n",
    "            cur //= 2\n",
    "            mi = min(mi, cur)\n",
    "            heapq.heappush(q, -cur)\n",
    "        ans = min(ans, -q[0] - mi)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\r\n",
    "class Solution:\r\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\r\n",
    "        nums=SortedList(num<<1 if num&1 else num for num in nums)\r\n",
    "\r\n",
    "        ans=nums[-1]-nums[0]\r\n",
    "        while not nums[-1]&1:\r\n",
    "            nums.add(nums.pop()>>1)\r\n",
    "            ans=min(ans, nums[-1]-nums[0])\r\n",
    "        \r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "# sys.set_int_max_str_digits(0)  # 大数的范围坑\n",
    "\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        lst = SortedList([num if num % 2 == 0 else num*2 for num in nums])\n",
    "        ans = inf\n",
    "        while True:\n",
    "            cur = lst[-1] - lst[0]\n",
    "            ans = ans if ans < cur else cur\n",
    "            if lst[-1] % 2:\n",
    "                break\n",
    "            lst.add(lst.pop()//2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]%2:\n",
    "                nums[i]*=-2\n",
    "            else:\n",
    "                nums[i]*=-1\n",
    "        nums=sorted(set(nums))\n",
    "        res=-nums[0]+nums[-1]\n",
    "        mmax=nums[-1]\n",
    "        while nums[0]%2==0:\n",
    "            tmp=int(nums[0]/2)\n",
    "            heapq.heapreplace(nums,tmp) \n",
    "            mmax=max(mmax,tmp)\n",
    "            res=min(res,-nums[0]+mmax)          \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        # Transform all numbers to even\n",
    "        nums = [num << (num & 1) for num in nums]\n",
    "        \n",
    "        sorted_nums = SortedList(nums)\n",
    "        min_num = min(nums)\n",
    "        \n",
    "        ans = float('inf')\n",
    "        \n",
    "        while len(sorted_nums) == len(nums):\n",
    "            max_num = sorted_nums[-1]\n",
    "            ans = min(ans, max_num - min_num)\n",
    "            \n",
    "            # Remove max number and divide it by 2 if it's still even\n",
    "            # then insert it back\n",
    "            sorted_nums.remove(max_num)\n",
    "            if max_num & 1 == 0:\n",
    "                sorted_nums.add(max_num // 2)\n",
    "                min_num = min(min_num, max_num // 2)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        nums = list(set(nums))\n",
    "        nums = [-num if num%2==0 else -num*2 for num in nums]\n",
    "        heapq.heapify(nums)\n",
    "        min_val = -max(nums)\n",
    "        res = -nums[0]+max(nums)\n",
    "        while -nums[0]%2 == 0:\n",
    "            tmp = -int(nums[0]/2 )\n",
    "            min_val = min(min_val, tmp)\n",
    "            heapq.heappop(nums)\n",
    "            heapq.heappush(nums, -tmp)\n",
    "            res = min(res, -nums[0]-min_val)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 1: Min Heap\n",
    "    time: O(nlogM + nlogn) for creating the heap, where M=max(nums),\n",
    "        O(n*logn*logM) for heappop() and heappush(), totally, O(n*logM*logn)\n",
    "    space: O(n)\n",
    "    \"\"\"\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        min_heap = []  # [(num, the cap of num)]\n",
    "        heap_cap = 0  # the maximum of the heap\n",
    "        res = float('inf')\n",
    "\n",
    "        # O(nlogM)\n",
    "        for num in nums:\n",
    "            temp = num\n",
    "            while num % 2 == 0:\n",
    "                num //= 2\n",
    "            min_heap.append((num, max(num * 2, temp)))\n",
    "            heap_cap = max(heap_cap, num)\n",
    "\n",
    "        # O(nlogn)\n",
    "        heapq.heapify(min_heap)\n",
    "\n",
    "        # O(n*logn*logM)\n",
    "        while len(min_heap) == len(nums):\n",
    "            num, n_max = heapq.heappop(min_heap)\n",
    "            res = min(res, heap_cap-num)\n",
    "            if num < n_max:\n",
    "                heapq.heappush(min_heap, (num*2, n_max))\n",
    "                heap_cap = max(heap_cap, num*2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        s = SortedSet([i * (i % 2 + 1) for i in nums])\n",
    "        res = s[-1] - s[0]\n",
    "        while not s[-1] & 1:\n",
    "            s.add(s.pop() >> 1)\n",
    "            res = min(res, s[-1] - s[0])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        s = SortedSet([i * (i % 2 + 1) for i in nums])\n",
    "        res = s[-1] - s[0]\n",
    "        while not s[-1] & 1:\n",
    "            s.add(s.pop() >> 1)\n",
    "            res = min(res, s[-1] - s[0])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        maxrange = []\n",
    "        for num in nums:\n",
    "            if num & 1:\n",
    "                maxrange.append(num * 2)\n",
    "            else:\n",
    "                maxrange.append(num)\n",
    "        for i in range(n):\n",
    "            while nums[i] % 2 == 0:\n",
    "                nums[i] = nums[i] // 2\n",
    "        nums = [(nums[i], maxrange[i]) for i in range(n)]\n",
    "        nums.sort()\n",
    "        # print(nums)\n",
    "        d = []\n",
    "        t = nums[-1][0]\n",
    "        for i, item in enumerate(nums):\n",
    "            num, maxn = item[0], item[1]\n",
    "            l, r = num, 2 * num\n",
    "            while r < t and r < maxn:\n",
    "                l = r\n",
    "                r = 2 * r\n",
    "            if r < t:\n",
    "                d.append([t - r, 10000000000])\n",
    "            else:\n",
    "                d.append([t - l, r - t])\n",
    "        # print(d)\n",
    "        d.sort(key = lambda x: x[0], reverse=True)\n",
    "        ans = d[0][0]\n",
    "        maxr = 0\n",
    "        for i in range(n):\n",
    "            temp = d[i][0] + maxr\n",
    "            ans = min(ans, temp)\n",
    "            maxr = max(maxr, d[i][1])\n",
    "        ans = min(ans, maxr)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        while nums[0] % 2:\n",
    "            heapq.heappush(nums, heappop(nums) * 2)\n",
    "        heap2 = [-x for x in nums]\n",
    "        heapq.heapify(heap2)\n",
    "        res = -heap2[0] - nums[0]\n",
    "        while heap2[0] % 2 == 0:\n",
    "            heappush(heap2, heap2[0] // 2)\n",
    "            heapq.heappush(nums, -heapq.heappop(heap2) // 2)\n",
    "            res = min(res, -heap2[0] - nums[0])\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, martrix: List[List[int]]) -> List[int]:\n",
    "        l, r = -10**9, 10**9\n",
    "        # 将每一行最小的都放到堆中，同时记录其所在的行号和列号，一共 n 个齐头并进\n",
    "        h = [(row[0], i, 0) for i, row in enumerate(martrix)]\n",
    "        heapq.heapify(h)\n",
    "        # 维护最大值\n",
    "        max_v = max(row[0] for row in martrix)\n",
    "\n",
    "        while True:\n",
    "            min_v, row, col = heapq.heappop(h)\n",
    "            # max_v - min_v 是当前的最大最小差值， r - l 为全局的最大最小差值。因为如果当前的更小，我们就更新全局结果\n",
    "            if max_v - min_v < r - l:\n",
    "                l, r = min_v, max_v\n",
    "            if col == len(martrix[row]) - 1: return [l, r]\n",
    "            # 更新指针，继续往后移动一位\n",
    "            heapq.heappush(h, (martrix[row][col + 1], row, col + 1))\n",
    "            max_v = max(max_v, martrix[row][col + 1])\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        matrix = [[] for _ in range(len(nums))]\n",
    "        for i, num in enumerate(nums):\n",
    "            if num & 1 == 1:\n",
    "                matrix[i] += [num, num * 2]\n",
    "            else:\n",
    "                temp = []\n",
    "                while num and num & 1 == 0:\n",
    "                    temp += [num]\n",
    "                    num //= 2\n",
    "                temp += [num]\n",
    "                matrix[i] += temp[::-1]\n",
    "        a, b = self.smallestRange(matrix)\n",
    "        return b - a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        values = [[] for _ in range(n)]\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num % 2:\n",
    "                # values[i].append(num)\n",
    "                # values[i].append(num * 2)\n",
    "                values[i] = [num, num * 2]\n",
    "            else:\n",
    "                tmp = []\n",
    "                while num % 2 == 0:\n",
    "                    tmp.append(num)\n",
    "                    num //= 2\n",
    "                tmp.append(num)\n",
    "                values[i] = tmp[::-1]\n",
    "        # print(values)\n",
    "\n",
    "        heap = []\n",
    "        for i in range(n):\n",
    "            heapq.heappush(heap, (values[i][0], 0, i))\n",
    "\n",
    "        curmax = max(heap)[0]\n",
    "        maxv = 10 ** 9 + 1\n",
    "        minv = 0\n",
    "\n",
    "        while True:\n",
    "            curmin, curi, curvi = heapq.heappop(heap)\n",
    "            if curmax - curmin < maxv - minv:\n",
    "                maxv, minv = curmax, curmin\n",
    "\n",
    "            if curi + 1 >= len(values[curvi]):\n",
    "                break\n",
    "\n",
    "            curi += 1\n",
    "            curmax = max(curmax, values[curvi][curi])\n",
    "            heapq.heappush(heap, (values[curvi][curi], curi, curvi))\n",
    "        return maxv - minv\n",
    "\n",
    "\n",
    "# [[1, 2], [2], [3, 6], [2, 4]]\n",
    "# [[1, 2], [1, 2], [3, 6], [1, 2, 4]]\n",
    "# class Solution:\n",
    "#     def minimumDeviation(self, nums: List[int]) -> int:\n",
    "#         n = len(nums)\n",
    "#         v = [list() for _ in range(n)]\n",
    "#         for i, num in enumerate(nums):\n",
    "#             if num & 1:\n",
    "#                 v[i].extend([num, num * 2])\n",
    "#             else:\n",
    "#                 while not nums[i] & 1:\n",
    "#                     v[i].append(nums[i])\n",
    "#                     nums[i] //= 2\n",
    "#                 v[i].append(nums[i])\n",
    "#                 v[i] = v[i][::-1]\n",
    "#         print(v)\n",
    "\n",
    "#         # ans = API.smallestRange(v)\n",
    "#         # return ans[1] - ans[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeviation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        values = [[] for _ in range(n)]\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num % 2:\n",
    "                # values[i].append(num)\n",
    "                # values[i].append(num * 2)\n",
    "                values[i] = [num, num * 2]\n",
    "            else:\n",
    "                tmp = []\n",
    "                while num % 2 == 0:\n",
    "                    tmp.append(num)\n",
    "                    num //= 2\n",
    "                tmp.append(num)\n",
    "                values[i] = tmp[::-1]\n",
    "        # print(values)\n",
    "\n",
    "        heap = []\n",
    "        for i in range(n):\n",
    "            heapq.heappush(heap, (values[i][0], 0, i))\n",
    "\n",
    "        curmax = max(heap)[0]\n",
    "        maxv = 10 ** 9 + 1\n",
    "        minv = 0\n",
    "\n",
    "        while True:\n",
    "            curmin, curi, curvi = heapq.heappop(heap)\n",
    "            if curmax - curmin < maxv - minv:\n",
    "                maxv, minv = curmax, curmin\n",
    "\n",
    "            if curi + 1 >= len(values[curvi]):\n",
    "                break\n",
    "\n",
    "            curi += 1\n",
    "            curmax = max(curmax, values[curvi][curi])\n",
    "            heapq.heappush(heap, (values[curvi][curi], curi, curvi))\n",
    "        return maxv - minv\n",
    "\n",
    "\n",
    "# [[1, 2], [2], [3, 6], [2, 4]]\n",
    "# [[1, 2], [1, 2], [3, 6], [1, 2, 4]]\n",
    "# class Solution:\n",
    "#     def minimumDeviation(self, nums: List[int]) -> int:\n",
    "#         n = len(nums)\n",
    "#         v = [list() for _ in range(n)]\n",
    "#         for i, num in enumerate(nums):\n",
    "#             if num & 1:\n",
    "#                 v[i].extend([num, num * 2])\n",
    "#             else:\n",
    "#                 while not nums[i] & 1:\n",
    "#                     v[i].append(nums[i])\n",
    "#                     nums[i] //= 2\n",
    "#                 v[i].append(nums[i])\n",
    "#                 v[i] = v[i][::-1]\n",
    "#         print(v)\n",
    "\n",
    "#         # ans = API.smallestRange(v)\n",
    "#         # return ans[1] - ans[0]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
